package leetcode.code0450;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public TreeNode deleteNode(TreeNode root, int key) {
		if (root == null) {
			return null;
		}
		int val = root.val;
		if (val > key) {
			root.left = this.deleteNode(root.left, key);
		} else if (val < key) {
			root.right = this.deleteNode(root.right, key);
		} else {
			if (root.left == null) {
				return root.right;
			}
			if (root.right == null) {
				return root.left;
			}
			TreeNode left = root.left;
			while (left.right != null) {
				left = left.right;
			}
			left.left = this.deleteNode(root.left, left.val);
			left.right = root.right;
			return left;
		}
		return root;
	}

	@Override
	public void debug4() {
		this.deleteNode(TreeArray.array2tree(H.str2array4("[3,2,4,1]")), 2);
//		this.deleteNode(TreeArray.array2tree(H.str2array4("[2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]")),1);
//		this.deleteNode(TreeArray.array2tree(H.str2array4("[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]")), 6);
//		[5,3,6,2,4,null,7]
//				3
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
////		[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		Integer num1 = 1000;
//		Integer num2 = 1000;
//		Integer num3 = 100;
//		Integer num4 = 100;
//		System.out.println(num1 == 1000);
//		System.out.println(num1 == num2);
//		System.out.println(num3 == num4);
		String name1 = new String("123");
		String name2 = name1;
		System.out.println(name1 == name2);
		System.out.println(name1.equals(name2));
		System.out.println(name1 == "123");
		System.out.println(name2 == "123");

//		[27,17,33,15,26,32,45,7,16,23,null,31,null,40,49,5,14,null,null,21,25,29,null,34,41,48,null,2,6,10,null,20,22,24,null,28,30,null,39,null,42,46,null,1,4,null,null,9,11,18,null,null,null,null,null,null,null,null,null,37,null,null,44,null,47,0,null,3,null,8,null,null,13,null,19,35,38,43,null,null,null,null,null,null,null,null,null,12,null,null,null,null,36]
//				49
	}

}
